Pera i Nada su napisali n celih brojeva na tabli i sada žele da igraju igru “Par-nepar”. U svakom potezu jedno od njih kaže broj i (i ∈ [0,n−1]), a drugo treba da odgovori da li je apsolutna razlika broja parnih i broja neparnih brojeva veća u delu niza pre ili posle pozicije i.
Napisati program koji će im pomoći da provere svoje odgovore tako što će za svaki indeks u nizu ispisati:
U slučaju da se pozicija nalazi na početku (kraju) niza, računati da je apsolutna razlika pre (posle) te pozicije 0. Vremenska i prostorna složenost treba da budu O(n).
Sa standardnog ulaza se unosi veličina niza n (1 ≤ n ≤ 100000), a zatim i n celih brojeva koji čine niz.
Za svaku poziciju u nizu ispisati -1, 0 ili 1 vodeći se uslovima iz postavke zadatka.
9
1 3 3 3 4 2 2 1 1 1 0 -1 -1 -1 -1 0 0 -1